\ifx\wholebook\relax \else

\documentclass[b5paper]{ctexart}
\usepackage[nomarginpar
  %, margin=.5in
]{geometry}

\addtolength{\oddsidemargin}{-0.05in}
\addtolength{\evensidemargin}{-0.05in}
\addtolength{\textwidth}{0.1in}
\usepackage[cn]{../../prelude}

\setcounter{page}{1}

\begin{document}

\title{选择排序}

\author{刘新宇
\thanks{{\bfseries 刘新宇 } \newline
  Email: liuxinyu99@hotmail.com \newline}
  }

\maketitle
\fi

%\markboth{选择排序}{基本算法}

\ifx\wholebook\relax
\chapter{选择排序}
\numberwithin{Exercise}{chapter}
\fi

\lstset{frame = single}
\label{introduction} \index{选择排序}
本章介绍另一种直观的排序方法——选择排序。它在性能上不如快速排序和归并排序等分治算法。我们给出选择排序性能的简要分析，并且从不同的角度加以改进，最终演进到堆排序，从而达到基于比较的排序算法性能上限$O(n \lg n)$。选择排序的思想可以在日常生活中找到。观察孩子们吃葡萄时，会发现两种类型的吃法：一种属于“乐观型”，每次吃掉最大的一颗；另一种属于“悲观型”，每次总吃掉最小的一颗。第一种孩子实际上按照由大到小的顺序吃葡萄；第二种按照由小到大的顺序吃葡萄。实际上，孩子们把葡萄按照大小进行了选择排序。选择排序的算法描述为：

\begin{enumerate}
\item 如果序列为空，排序结果也为空；
\item 否则，找到最小的元素，将其附加到结果的后面。
\end{enumerate}

这一算法产生升序结果。如果每次选择最大的元素，则结果是降序的。我们可以用抽象的比较操作实现排序。

\be
\begin{array}{rcl}
sort\ [\ ]  & = & [\ ] \\
sort\ A & = & m : sort\ (A - [m]) \quad \text{其中}\ m = \min\ A
\end{array}
\ee

$A - [m]$从序列$A$中去除元素$m$。对应的命令式描述为：

\begin{algorithmic}[1]
\Function{Sort}{$A$}
  \State $X \gets [\ ]$
  \While{$A \neq [\ ]$}
    \State $x \gets$ \Call{Min}{$A$}
    \State \Call{Del}{$A, x$}
    \State \Call{Append}{$X, x$}
  \EndWhile
  \State \Return $X$
\EndFunction
\end{algorithmic}

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.8]{img/ssort}
  \caption{左侧部分为已序元素，不断从剩余部分选择最小元素附加在左侧尾部}
  \label{fig:sel-sort}
\end{figure}

\cref{fig:sel-sort}描述了选择排序的过程。作为改进，我们可以在$A$中进行原地排序，去掉列表$X$。将最小的元素保存在$A[1]$，将次小的元素保存在$A[2]$……。可以通过交换位置实现：当找到第$i$小的元素后，将它和$A[i]$交换。

\begin{algorithmic}[1]
\Function{Sort}{$A$}
  \For{$i \gets 1$ to $|A|$}
    \State $m \gets$ \Call{Min-At}{$A, i$}
    \State \textproc{Exchange} $A[i] \leftrightarrow A[m]$
  \EndFor
\EndFunction
\end{algorithmic}

令$A = [a_1, a_2, ..., a_n]$，当处理第$i$个元素时，$[a_1, a_2, ..., a_{i-1}]$都已排序。我们找到$[a_i, a_{i+1}, ..., a_n]$中的最小元素，将其和$a_i$交换，这样第$i$个位置就保存了正确的元素。重复这一过程直到最后一个元素。\cref{fig:in-place-ssort}描述了这一思路。

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[scale=0.8]
    \draw (0, 0) rectangle (3.5,1) node[pos=.5] {...已序元素...};
    \draw (4, 0) rectangle (5, 1) node (x) [pos=.5] {$x$};
    \draw (5, 0) rectangle (6, 1) node[pos=.5] {...};
    \draw (6, 0) rectangle (7, 1) node (min) [pos=.5] {$\min$};
    \draw (7, 0) rectangle (8, 1) node[pos=.5] {...};
    \draw[thick, <->] (x) edge[bend left=45] node [above] {交换} (min);
  \end{tikzpicture}
  \caption{左侧部分为已序元素，不断从剩余部分找到最小的交换到正确位置}
  \label{fig:in-place-ssort}
\end{figure}

\section{查找最小元素}
\index{选择排序!查找最小元素}

我们可以用比较——交换方法在一组元素中寻找最小值。将元素编号为$1, 2, ..., n$。比较编号为1，2的两个元素，选择较小的留下与编号为3的元素比较……重复这一步骤直到第$n$号元素。这一方法适合处理数组。

\begin{algorithmic}[1]
\Function{Min-At}{$A, i$}
  \State $m \gets i$
  \For{$i \gets m + 1 $ to $|A|$}
    \If{$A[i] < A[m]$}
      \State $m \gets i$
    \EndIf
  \EndFor
  \State \Return $m$
\EndFunction
\end{algorithmic}

\index{选择排序!递归查找最小元素}
\textproc{Min-At}查找片断$A[i...]$中最小元素的位置$m$。令$m$指向第一个元素$A[i]$，并逐一检查元素$A[i+1], A[i+2], ...$。也可以用递归的方法在在一组元素$L$中查找最小值。如果$L$只有一个元素，它就是最小值。否则从$L$中取出一个元素$x$，然后在剩余部分中递归找到最小值$y$。$x$、$y$中较小的一个就是最终的最小值。

\be
\begin{array}{rcl}
\min\ [x] & = & (x, [\ ]) \\
\min\ (x \cons xs) & = & \begin{cases}
  x < y: & (x, xs),\ \text{其中}:\ (y, ys) = \min\ xs \\
  \text{否则}: & (y,\ x \cons ys)
\end{cases}
\end{array}
\ee

可以进一步用尾递归优化。将全部元素分成两组：$A$、$B$。开始时$A$为空（$[\ ]$），$B$包含全部元素。我们从$B$中任选两个元素比较，将较大的放入$A$，而留下较小的记为$m$。此后不断从$B$中任取一个元素，和$m$对比直到$B$变成空。这时，$m$就是最小值。在任何时候有不变关系：$L = A \doubleplus [m] \doubleplus B$，对任意$a \in A, b \in B$有$a \leq m \leq b$。

\be
\min\ (x \cons xs) = min'\ [\ ]\ x\ xs
\ee

其中：

\be
\begin{array}{rcl}
min'\ as\ m\ [\ ] & = & (m, as) \\
min'\ as\ m\ (b \cons bs) & = & \begin{cases}
  b < m: & min'\ (m \cons as)\ b\ bs \\
  \text{否则}: & min'\ (b \cons as)\ m\ bs \\
\end{cases}
\end{array}
\ee

函数$\min$返回一对值：最小元素和剩余元素列表。这样选择排序就可以实现为：

\be
\begin{array}{rcl}
sort\ [\ ] & = & [\ ] \\
sort\ xs   & = & m : (sort\ xs'),\ \text{其中}:\ (m, xs') = \min\ xs \\
\end{array}
\ee

\subsection{选择排序的性能}

选择排序在每轮中检查所有未排好的元素以挑选出最小值。总共进行了$n$次挑选，$n + (n-1) + (n-2) + ... + 1$次比较，时间复杂度为$O(\dfrac{n(n+1)}{2}) = O(n^2)$。和插入排序相比，选择排序在最好、最差和平均情况下的性能是相同的，而插入排序在最好情况下性能为线性时间$O(n)$（元素逆序存储在一个链表中），最差情况下性能为平方时间$O(n^2)$。

\begin{Exercise}[label={ex:basic-sel-sort}]
\Question{下面的尾递归查找最小值实现有何问题？
\[
\begin{array}{rcl}
min'\ as\ m\ [\ ] & = & (m, as) \\
min'\ as\ m\ (b \cons bs) & = & \begin{cases}
  b < m: & min'\ (as \doubleplus [m])\ b\ bs \\
  \text{否则}: & min'\ (as \doubleplus [b])\ m\ bs \\
\end{cases}
\end{array}
\]
}
\Question{实现原地选择排序程序。}
\end{Exercise}

\begin{Answer}[ref = {ex:basic-sel-sort}]
\Question{这里需要用链接而不是追加。追加操作的复杂度是线性的，和序列的长度成正比，而链接是常数时间的。}
\Question{实现原地选择排序程序。

\begin{Bourbaki}
Void sort([K] xs) {
    var n = length(xs)
    for var i = 0 to n - 1 {
        var m = i
        for Int j = i + 1 to n - 1 {
            if xs[j] < xs[m] then m = j
        }
        swap(xs[i], xs[m])
    }
}
\end{Bourbaki}
}
\end{Answer}

\section{改进}

为了支持升序、降序、和不同的比较，我们可以将比较操作抽出作为参数$\lhd$。

\be
\begin{array}{rcl}
sortBy \lhd\ [\ ] & = & [\ ] \\
sortBy \lhd\ xs & = & m : sortBy\ \lhd\ xs',\ \text{其中}:\ (m, xs') = minBy\ \lhd\ xs \\
\end{array}
\ee

“最小值”也使用$\lhd$进行比较：

\be
\begin{array}{rcl}
minBy\ \lhd\ [x] & = & (x, [\ ]) \\
minBy\ \lhd\ (x \cons xs) & = & \begin{cases}
  x \lhd y: & (x, xs),\ \text{其中}:\ (y, ys) = minBy\ \lhd\ xs \\
  \text{否则}: & (y,\ x:ys)
\end{cases}
\end{array}
\ee

\index{严格弱序} \label{sec:strict-weak-order}
对于一组整数，传入小于号得到升序结果：$sortBy\ (<)\ [3, 1, 4, ...]$。这里要求$\lhd$满足严格弱序\cite{wiki-sweak-order}条件：

\begin{itemize}
\item 非自反性：对任何$x$，$x \nless x$；
\item 非对称性：对任何$x$、$y$，若$x < y$，则$y \nless x$；
\item 传递性：对任何$x$、$y$、$z$，若$x < y$且$y < z$，则$x < z$。
\end{itemize}

命令式原地选择排序遍历所有的元素，并在内冲循环中查找最小值：

\begin{algorithmic}[1]
\Procedure{Sort}{$A$}
  \For{ $i \gets 1$ to $|A|$}
    \State $m \gets i$
    \For{$j \gets i+1$ to $|A|$}
      \If{$A[i] < A[m]$}
        \State $m \gets i$
      \EndIf
    \EndFor
    \State \textproc{Exchange} $A[i] \leftrightarrow A[m]$
  \EndFor
\EndProcedure
\end{algorithmic}

前$n-1$个元素排好后，最后一个元素必然是第$n$大的。无需再进行一次最小值查找。这样可以减少一次外重循环。另外，如果第$i$大的元素恰好是$A[i]$，则无需交换：

\begin{algorithmic}[1]
\Procedure{Sort}{$A$}
  \For{ $i \gets 1$ to $|A|-1$}
    \State $m \gets i$
    \For{$j \gets i+1$ to $|A|$}
      \If{$A[i] < A[m]$}
        \State $m \gets i$
      \EndIf
    \EndFor
    \If{$m \neq i$}
      \State \textproc{Exchange} $A[i] \leftrightarrow A[m]$
    \EndIf
  \EndFor
\EndProcedure
\end{algorithmic}

\subsection{鸡尾酒排序}
\index{鸡尾酒排序}

高德纳给出了另一种实现\cite{TAOCP}：每次不是查找最小元素，而是最大元素，将其放在末尾位置。如\cref{fig:knuth-ssort}所示，任何时候，最右侧的元素都是已序的。算法扫描未排序元素，定位到其中的最大值，然后交换到未排序部分的末尾。

\begin{algorithmic}[1]
\Procedure{Sort'}{$A$}
  \For{ $i \gets |A|$ down-to $2$}
    \State $m \gets i$
    \For{$j \gets 1$ to $i-1$}
      \If{$A[m] < A[i]$}
        \State $m \gets i$
      \EndIf
    \EndFor
    \State \textproc{Exchange} $A[i] \leftrightarrow A[m]$
  \EndFor
\EndProcedure
\end{algorithmic}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[scale=0.8]
    \draw (5, 0) rectangle (6, 1) node[pos=.5] {...};
    \draw (6, 0) rectangle (7, 1) node (max) [pos=.5] {$\max$};
    \draw (7, 0) rectangle (8, 1) node[pos=.5] {...};
    \draw (8, 0) rectangle (9, 1) node (x) [pos=.5] {$x$};
    \draw (10,0) rectangle (13.5,1) node[pos=.5] {...已序元素...};
    \draw[thick, <->] (x) edge[bend right=45] node [above] {交换} (max);
  \end{tikzpicture}
  \caption{每次选择最大的元素放到末尾}
  \label{fig:knuth-ssort}
\end{figure}

进一步，每次扫描可以同时查找最小、最大值，将最小值放到开头，最大值放到末尾。这样可以将外重循环次数减半。这一算法称为“鸡尾酒排序”。如\cref{fig:cock-tail-sort}所示。

\begin{algorithmic}[1]
\Procedure{Sort}{$A$}
  \For{$i \gets 1 $ to $\lfloor \dfrac{|A|}{2} \rfloor$}
    \State $min \gets i$
    \State $max \gets |A| + 1 - i$
    \If{$A[max] < A[min]$}
      \State \textproc{Exchange} $A[min] \leftrightarrow A[max]$
    \EndIf
    \For{$j \gets i + 1$ to $|A| - i$}
      \If{$A[j] < A[min]$}
        \State $min \gets j$
      \EndIf
      \If{$A[max] < A[j]$}
        \State $max \gets j$
      \EndIf
    \EndFor
    \State \textproc{Exchange} $A[i] \leftrightarrow A[min]$
    \State \textproc{Exchange} $A[|A|+1-i] \leftrightarrow A[max]$
  \EndFor
\EndProcedure
\end{algorithmic}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[scale=0.8]
    \draw (0,0) rectangle (3.5,1) node[pos=.5] {...已序较小元素...};
    \draw (4, 0) rectangle (5, 1) node (x) [pos=.5] {$x$};
    \draw (5, 0) rectangle (6, 1) node[pos=.5] {...};
    \draw (6, 0) rectangle (7, 1) node (max) [pos=.5] {$\max$};
    \draw (7, 0) rectangle (8, 1) node[pos=.5] {...};
    \draw (8, 0) rectangle (9, 1) node (min) [pos=.5] {$\min$};
    \draw (9, 0) rectangle (10, 1) node[pos=.5] {...};
    \draw (10, 0) rectangle (11, 1) node (y) [pos=.5] {$y$};
    \draw (12,0) rectangle (15.5,1) node[pos=.5] {...已序较大元素...};
    \draw[thick, <->] (x) edge[bend right=45] node [below] {交换} (min);
    \draw[thick, <->] (y) edge[bend right=45] node [above] {交换} (max);
  \end{tikzpicture}
  \caption{一次扫描同时定位出最小和最大元素，然后将它们放到正确的位置}
  \label{fig:cock-tail-sort}
\end{figure}

在内重循环开始前，如果最右侧小于最左侧的元素，需要进行交换。这是因为扫描范围不包括两端。也可以用递归的方式实现鸡尾酒排序：

\begin{enumerate}
  \item 若待排序的序列为空或者仅含有一个元素，排序结果为原序列；
  \item 否则，找到最小和最大值，分别放到开头和结尾位置，然后递归地将剩余元素排序。
\end{enumerate}

\be
\begin{array}{rcl}
sort\ [\ ] & = & [\ ] \\
sort\ [x] & = & [x] \\
sort\ xs & = & a : (sort\ xs') \doubleplus [b], \text{其中}: (a, b, xs') = \textit{min-max}\ xs \\
\end{array}
\ee

其中，函数\textit{min-max}从序列中抽取出最小值和最大值：

\be
\textit{min-max}\ (x \cons y \cons xs) = foldr\ sel\ (\min\ x\ y, \max\ x\ y, [\ ])\ xs
\ee

我们选取前两个元素作为已找到的最小值$x_0$，最大值$x_1$，用$foldr$扫描序列，其中$sel$定义为：

\[
sel\ x\ (x_0, x_1, xs) = \begin{cases}
  x < x_0: & (x, x_1, x_0 \cons xs) \\
  x_1 < x: & (x_0, x, x_1 \cons xs) \\
  \text{否则}: & (x_0, x_1, x \cons xs) \\
\end{cases}
\]

尽管\textit{min-max}只需要线性时间$O(n)$，但$\doubleplus[b]$的代价较大。如\cref{fig:cock-tail-sort}所示，令左侧$A$包含较小的已序元素；右侧$B$包含较大的已序元素。用$A$和$B$作为累积器，可将排序转换为尾递归：

\be
\begin{array}{rcl}
sort'\ A\ B\ [\ ] & = & A \doubleplus B \\
sort'\ A\ B\ [x]  & = & A \doubleplus (x \cons B) \\
sort'\ A\ B\ (x \cons xs) & = & sort'\ (A \doubleplus [x_0])\ xs'\ (x_1 \cons B), \text{其中：}(x_0, x_1, xs') = \textit{min-max}\ xs \\
\end{array}
\ee

传入空的$A$、$B$启动排序：$sort = sort'\ [\ ]\ [\ ]$。追加操作仅仅发生在$A \doubleplus [x_0]$；而$x_1$则被链结到$B$的前面。为了消除追加操作，我们将$A$保存为逆序$\overleftarrow{A}$，这样就可以将$x_0$链结到前面。我们有如下等价关系：

\be
\begin{array}{rcl}
A' & = & A \doubleplus [x] \\
   & = & reverse\ (x : reverse\ A) \\
   & = & reverse\ (x : \overleftarrow{A}) \\
   & = & \overleftarrow{ x : \overleftarrow{A}}
\end{array}
\ee

最后执行一次反转操作将$\overleftarrow{A'}$转换回$A'$。根据这一思路，可改进如下：

\be
\begin{array}{rcl}
sort'\ A\ B\ [\ ] & = & (reverse\ A) \doubleplus B \\
sort'\ A\ B\ [x]  & = & (reverse\ x \cons A) \doubleplus B \\
sort'\ A\ B\ (x \cons xs) & = & sort'\ (x_0 \cons A)\ xs'\ (x_1 \cons B) \\
\end{array}
\ee

\section{继续改进}

虽然鸡尾酒排序将循环次数减半，但时间复杂度仍然是$O(n^2)$。通过比较进行排序，需要检查元素间的大小顺序，外重循环是必须的。必需每次扫描全部元素以查找最小值么？在第一次查找最小元素时，我们遍历了序列，知道哪些元素相对较小，哪些相对较大。但在后继查找中，我们没有复用这些相对大小的信息，而是从头开始再次遍历。进一步改进的关键在于重用已有的结果。其中一种思路来自体育竞赛。

\subsection{锦标赛淘汰法}
\index{锦标赛淘汰法}

足球世界杯每四年举办一次。来自各个大洲的32支球队最终进入决赛。1982年前，决赛阶段只有16支球队。我们回到1978年，并且想像一种特殊的方法来决定冠军：在第一轮比赛中，所有参赛球队被分为8组进行比赛；比赛产生8支获胜球队，其余8支被淘汰。接下来，在第二轮比赛中，8支球队被分成4组。比赛产生4支获胜球队；然后这4支球队分成两对，比赛产生最终的两支球队争夺冠军。经过4轮比赛，冠军就可产生。总共的比赛场次为：$8+4+2+1 = 15$。但是我们并不满足仅仅知道谁是冠军，我们还想知道哪支球队是亚军。有人会问最后一场比赛中被冠军击败的队伍不是亚军么？在真实的世界杯中，的确如此。但是这个规则在某种程度上并不公平。我们常常听说过“死亡之组”，假设巴西队一开始就和德国队进行比赛。虽然它们两个都是强队，但是必须有一支在一上来就被淘汰。这支被淘汰的球队，很可能会打败除冠军外的其他所有球队。\cref{fig:tournament-tree-1}描述了这一情况。

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.4]{img/tournament-tree-1}
  \caption{元素15在第一轮就被淘汰}
  \label{fig:tournament-tree-1}
\end{figure}

每支队伍有一个代表其实力的数字。数字越大，实力越强。假设数字较大的队永远会战胜数字较小的队（虽然现实中不会这样）。代表冠军的数字为16，根据假设的规则，数字14不是亚军，而是在第一轮就被淘汰的15。我们需要一种快速的方法在锦标赛树中找到次大值。此后，不断重复这一方法，找出第三大，第四大……就可以完成基于选择的排序。把冠军的数字修改成一个很小的值（例如$-\infty$），这样以后它不会被选中，第二名就会成为新的冠军。假设有$2^m$支球队，$m$是自然数，仍然需要$2^{m-1} + 2^{m-2} + ... + 2 + 1 = 2^m-1$次比较才能产生新的冠军，这和第一次寻找冠军花费的代价相同。实际上，我们无需再进行自底向上的比较。锦标赛树中保存了足够的顺序信息。实力第二强的队，一定在某个时刻被冠军击败，否则它就会是最终的冠军。因此我们可以从锦标赛树的根节点出发，沿着产生冠军的路径向叶子方向遍历，在这条路径上寻找第二强的队。\cref{fig:tournament-tree-1}中，这条路径被标记为灰色，需要检查的元素包括$[14, 13, 7, 15]$，这一思路可以描述如下：

\begin{enumerate}
\item 从待排序元素构建一棵锦标赛树，冠军（最大值）位于树根；
\item 取出树根，自顶向下沿着冠军路径将最大值替换为$-\infty$；
\item 自底向上沿着刚才的路径回溯，找出新的冠军，并将其置于树根；
\item 重复步骤2，直到所有的元素都被取出。
\end{enumerate}

\captionsetup[subfigure]{labelformat=empty, margin=10pt}
\begin{figure}[htbp]
  \centering
  \subcaptionbox{取出16，将其替换为$-\infty$，15上升为新的根}{\includegraphics[scale=0.4]{img/tournament-tree-2}} \\
  \subcaptionbox{取出15，将其替换为$-\infty$，14上升为新的根}{\includegraphics[scale=0.4]{img/tournament-tree-3}} \\
  \subcaptionbox{取出14，将其替换为$-\infty$，13上升为新的根}{\includegraphics[scale=0.4]{img/tournament-tree-4}}
  \caption{锦标赛树排序的前几步}
  \label{fig:tournament-tree-4}
\end{figure}
\captionsetup[subfigure]{labelformat=parens}

为了对一组元素排序，我们先从它们构造一棵锦标赛树，然后不断取出冠军，\cref{fig:tournament-tree-4}给出了这一排序的前几个步骤。复用二叉树的定义，为了方便回溯，每个节点需要指向它的父节点。如果元素数目$n$不是$2^m$，两两比较后会剩余元素没有“对手”，“轮空”进入下一轮。为了构造锦标赛树，从每个元素构造一棵叶子得到$n$棵二叉树。然后每次取出两棵树$t_1$、$t_2$，构造一棵更大的二叉树$t$。其中$t$的根为$\max(key(t_1), key(t_2))$，左右子树为$t_1$、$t_2$。重复这一步骤得到一组新树，每棵的高度增加1，如有剩余则进入下一轮（奇数棵）。这样每轮过后，树减半为$\lfloor \dfrac{n}{2} \rfloor$、$\lfloor \dfrac{n}{4} \rfloor$……持续同样的操作最终得到一棵锦标赛树。总时间复杂度为$O(n + \dfrac{n}{2} + \dfrac{n}{4} + ... ) = O(2n) = O(n)$。

\begin{algorithmic}[1]
\Function{Build-Tree}{$A$}
  \State $T \gets [\ ]$
  \For{each $x \in A$}
    \State \textproc{Append}($T$, \Call{Node}{NIL, $x$, NIL})
  \EndFor
  \While{$|T| > 1$}
    \State $T' \gets [\ ]$
    \For{every $t_1, t_2 \in T$}
      \State $k \gets$ \textproc{Max}(\Call{Key}{$t_1$}, \Call{Key}{$t_2$})
      \State \textproc{Append}($T'$, \Call{Node}{$t_1$, $k$, $t_2$})
    \EndFor
    \If{|T| is odd}
      \State \textproc{Append}($T'$, \Call{Last}{$T$})
    \EndIf
    \State $T \gets T'$
  \EndWhile
  \State \Return $T[1]$
\EndFunction
\end{algorithmic}

每次取出锦标赛树的根节点后，我们自顶向下将其替换为$-\infty$，然后在通过父节点向上回溯，找出新的最大值。

\begin{algorithmic}[1]
\Function{Pop}{$T$}
  \State $m \gets$ \Call{Key}{$T$}
  \State \Call{Key}{$T$} $\gets -\infty$
  \While{$T$ is not leaf}  \Comment{自顶向下将$m$替换为$-\infty$}
    \If{\textproc{Key}(\Call{Left}{$T$}) $ = m$}
      \State $T \gets$ \Call{Left}{$T$}
    \Else
      \State $T \gets$ \Call{Right}{$T$}
    \EndIf
    \State \Call{Key}{$T$} $\gets -\infty$
  \EndWhile
  \While{\Call{Parent}{$T$} $\neq$ NIL} \Comment{自底向上决出新冠军}
    \State $T \gets$ \Call{Parent}{$T$}
    \State \Call{Key}{$T$} $\gets$ \textproc{Max}(\textproc{Key}(\Call{Left}{$T$}), \textproc{Key}(\Call{Right}{$T$}))
  \EndWhile
  \State \Return $(m, T)$ \Comment{返回最大元素和更新的树}
\EndFunction
\end{algorithmic}

\textproc{Pop}上下处理两遍，自顶向下一遍，接着自底向上沿着“冠军之路”一遍。由于锦标赛树是平衡的，路径的长度，也就是树的高度为$O(\lg n)$。时间复杂度为$O(\lg n)$。下面是锦标赛排序的实现。算法首先用$O(n)$时间构建一棵锦标赛树，然后执行$n$次弹出操作，逐一从树中取出最大值。每次弹出操作的性能为$O(\lg n)$，锦标赛排序的总时间复杂度为$O(n \lg n)$。

\begin{algorithmic}[1]
\Procedure{Sort}{$A$}
  \State $T \gets$ \Call{Build-Tree}{$A$}
  \For{$i \gets |A|$ down to $1$}
    \State $(A[i], T) \gets$ \Call{Pop}{$T$}
  \EndFor
\EndProcedure
\end{algorithmic}

也可以递归实现锦标赛排序。复用二叉树的定义。令一棵非空的树为$(l, k, r)$，其中$k$为元素，$l$、$r$是左右子树。定义$wrap\ x = (\nil, x, \nil)$构造一个叶子节点。这样就可以从列表$xs$构造出$n$棵叶子：$ts = map\ wrap\ xs$。构造锦标赛树时，比较两棵树$t_1$、$t_2$，选择较大的作为根，$t_1$、$t_2$作为左右子树。

\be
merge\ t_1\ t_2 = (t_1, \max\ k_1\ k_2, t_2)
\ee

其中$k_1 = key\ t_1, k_2 = key\ t_2$。函数$build\ ts$不断取出两棵树进行合并，最终构造出锦标赛树。

\be
\begin{array}{rcl}
build\ [\ ] & = & \nil \\
build\ [t]  & = & t \\
build\ ts & = & build\ (\textit{pairs}\ ts) \\
\end{array}
\ee

其中：

\be
\begin{array}{rcl}
\textit{pairs}\ (t_1 \cons t_2 \cons ts) & = & (merge\ t_1\ t_2) : \textit{pairs}\ ts \\
\textit{pairs}\ ts & = & ts \\
\end{array}
\ee

为了取得冠军，我们检查左右子树，看哪一棵和根节点的元素相等。然后递归地从子树中取出冠军直到叶子节点。最后将叶子中的元素替换为$-\infty$。

\be
\begin{array}{rcl}
pop\ (\nil, k, \nil) & = & (\nil, -\infty, \nil) \\
pop\ (l, k, r) & = & \begin{cases}
  k = key\ l: & (l', \max\ (key\ l')\ (key\ r), r), \text{其中}\ l' = pop\ l \\
  k = key\ r: & (l,  \max\ (key\ l)\ (key\ r'), r'), \text{其中}\ r' = pop\ r \\
\end{cases}
\end{array}
\ee

排序的过程不断从一棵锦标赛树弹出冠军（降序）：

\be
\begin{array}{rcl}
sort\ \nil & = & [\ ] \\
sort\ (l, -\infty, r) & = & [\ ]  \\
sort\ t & = & (key\ t) : sort\ (pop\ t) \\
\end{array}
\label{eq:tsort}
\ee

\begin{Exercise}[label={ex:tournament-tree-sort}]
\Question{将递归的锦标赛排序实现为升序。}\label{ex:parameterized-tournament-tree-sort}
\Question{锦标赛树排序可以处理相等元素么？它是稳定排序么？}
\Question{比较锦标赛树排序和二叉搜索树排序，它们的时间和空间效率如何。}
\Question{比较堆排序和锦标赛树排序，它们的时间和空间效率如何。}
\end{Exercise}

\begin{Answer}[ref = {ex:tournament-tree-sort}]
\Question{将递归的锦标赛排序实现为升序。

把$max$和$-\infty$替换为$min$和$\infty$就可以实现升序排序。我们可以进一步把它们抽象成参数：

\begin{Haskell}
minBy p a b = if p a b then a else b

merge p t1 t2 = Br t1 (minBy p (key t1) (key t2)) t2

fromListWith p xs = build $ map wrap xs where
  build [] = Empty
  build [t] = t
  build ts = build $ pair ts
  pair (t1:t2:ts) = (merge p t1 t2) : pair ts
  pair ts = ts

popWith p inf = delMin where
  delMin (Br Empty _ Empty) = Br Empty inf Empty
  delMin (Br l k r) | k == key l = let l' = delMin l in
                      Br l' (minBy p (key l') (key r)) r
                    | k == key r = let r' = delMin r in
                      Br l (minBy p (key l) (key r')) r'

toListWith p inf = flat where
  flat Empty = []
  flat t | inf == key t = []
         | otherwise = (top t) : (flat $ popWith p inf t)

sortBy p inf xs = toListWith p inf $ fromListWith p xs where
\end{Haskell}

$sortBy\ (<)\ \infty$定义了升序排序，而$sortBy\ (>)\ -\infty$定义了降序排序。
}
\Question{锦标赛树排序可以处理相等元素么？它是稳定排序么？

可以处理相等元素。使用\cref{ex:parameterized-tournament-tree-sort}的结果，$sortBy\ (\leq)\ \infty$即可实现含有相等元素的升序排序。它不是稳定排序。
}
\Question{比较锦标赛树排序和二叉搜索树排序，它们的时间和空间效率如何。

它们的时间复杂度都是$O(n \lg n)$，空间复杂度都是$O(n)$。区别在于，二叉搜索树建立后不再改变（除非插入、删除）。而锦标赛树在排序后变成含有$n$个无穷节点的空树。
}
\Question{比较堆排序和锦标赛树排序，它们的时间和空间效率如何。

它们的时间复杂度都是$O(n \lg n)$，空间复杂度都是$O(n)$。区别在于，堆排序结束后堆变空，而锦标赛树在排序后仍然占据$O(n)$的空间。
}
\end{Answer}

\subsection{改进为堆排序}

锦标赛树将时间复杂度提高到$O(n \lg n)$，达到了基于比较的排序算法上限\cite{TAOCP}。这里仍有改进的空间。排序完成后，锦标赛树的所有节点都变成了负无穷，这棵二叉树不再含有任何有效信息，但却占据了空间。有没有办法在弹出后释放节点呢？如果待排序的元素有$n$个，锦标赛树实际上占用了$2n$个节点。其中有$n$个叶子和$n$个分支。有没有办法能节约一半空间呢？如果当根节点为负无穷时，认为树为空，并将$key$重命名为$top$，那么\cref{eq:tsort}就可以进一步转化为更通用的形式：

\be
\begin{array}{rcl}
sort\ \nil & = & [\ ] \\
sort\ t & = & (top\ t) : sort\ (pop\ t) \\
\end{array}
\ee

这和堆排序定义完全一样。堆总在顶部保存最小（或最大）值，并且提供了快速的弹出操作。使用数组的二叉堆实际上将树结构“编码”成数组索引，因此除了$n$个单元外，无需任何额外的空间。函数式的堆，如左偏堆和伸展堆也只需要$n$个节点。我们将在下一章介绍更多种类的堆，它们在许多情况下都有很好的性能。

\section{附录：例子程序}

尾递归实现的选择排序：
\begin{Haskell}
sort [] = []
sort xs = x : sort xs'
  where
    (x, xs') = extractMin xs

extractMin (x:xs) = min' [] x xs
  where
    min' ys m [] = (m, ys)
    min' ys m (x:xs) = if m < x then min' (x:ys) m xs
                                else min' (m:ys) x xs
\end{Haskell}

鸡尾酒排序：

\begin{lstlisting}[language = Bourbaki]
[A] cocktailSort([A] xs) {
    Int n = length(xs)
    for Int i = 0 to n / 2 {
        var (mi, ma) = (i, n - 1 -i)
        if xs[ma] < xs[mi] then swap(xs[mi], xs[ma])
        for Int j = i + 1 to n - 1 - i {
            if xs[j] < xs[mi] then mi = j
            if xs[ma] < xs[j] then ma = j
        }
        swap(xs[i], xs[mi])
        swap(xs[n - 1 - i], xs[ma])
    }
    return xs
}
\end{lstlisting}

尾递归的鸡尾酒排序：

\begin{Haskell}
csort xs = cocktail [] [] xs
  where
    cocktail as bs []  = reverse as ++ bs
    cocktail as bs [x] = reverse (x:as) ++ bs
    cocktail as bs xs  = let (mi, ma, xs') = minMax xs
                         in cocktail (mi:as) (ma:bs) xs'

minMax (x:y:xs) = foldr sel (min x y, max x y, []) xs
  where
    sel x (mi, ma, ys) | x < mi = (x, ma, mi:ys)
                       | ma < x = (mi, x, ma:ys)
                       | otherwise = (mi, ma, x:ys)
\end{Haskell}

复用二叉树构造锦标赛树：

\begin{lstlisting}[language = Bourbaki]
Node<T> build([T] xs) {
    [T] ts = []
    for x in xs {
        append(ts, Node(null, x, null))
    }
    while length(ts) >  1 {
        [T] ts' = []
        for l, r in ts {
            append(ts', Node(l, max(l.key, r.key), r))
        }
        if odd(length(ts)) then append(ts', last(ts))
        ts = ts'
    }
    return ts[0];
}
\end{lstlisting}

从锦标赛树取出冠军：

\begin{lstlisting}[language = Bourbaki]
T pop(Node<T> t) {
    T m = t.key
    t.key = -INF
    while not isLeaf(t) {
        t = if t.left.key == m then t.left else t.right
        t.key = -INF
    }
    while (t.parent != null) {
        t = t.parent
        t.key = max(t.left.key, t.right.key)
    }
    return (m, t);
}
\end{lstlisting}

锦标赛树排序：

\begin{lstlisting}[language = Bourbaki]
void sort([A] xs) {
    Node<T> t = build(xs)
    for Int n = length(xs) - 1 downto 0 {
        (xs[n], t) = pop(t)
    }
}
\end{lstlisting}

递归的锦标赛排序（降序）：

\begin{Haskell}
data Tr a = Empty | Br (Tr a) a (Tr a)

data Infinite a = NegInf | Only a | Inf deriving (Eq, Ord)

key (Br _ k _ ) = k

wrap x = Br Empty (Only x) Empty

merge t1@(Br _ k1 _) t2@(Br _ k2 _) = Br t1 (max k1 k2) t2

fromList = build . (map wrap) where
  build [] = Empty
  build [t] = t
  build ts = build (pairs ts)
  pairs (t1:t2:ts) = (merge t1 t2) : pair ts
  pairs ts = ts

pop (Br Empty _ Empty) = Br Empty NegInf Empty
pop (Br l k r) | k == key l = let l' = pop l in Br l' (max (key l') (key r)) r
               | k == key r = let r' = pop r in Br l (max (key l) (key r')) r'

toList Empty = []
toList (Br _ Inf _) = []
toList t@(Br _ Only k _) = k : toList (pop t)

sort = toList . fromList
\end{Haskell}

\ifx\wholebook\relax\else
\section{参考答案}
\shipoutAnswer

\begin{thebibliography}{99}

\bibitem{TAOCP}
Donald E. Knuth. ``The Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition)''. Addison-Wesley Professional; 2 edition (May 4, 1998) ISBN-10: 0201896850 ISBN-13: 978-0201896855

\bibitem{CLRS}
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
``Introduction to Algorithms, Second Edition''. ISBN:0262032937. The MIT Press. 2001 （《算法导论》中文版）

\bibitem{wiki-sweak-order}
Wikipedia. ``Strict weak order''. \url{https://en.wikipedia.org/wiki/Strict_weak_order}

\end{thebibliography}

\expandafter\enddocument
\fi
